package com.li.suanfa;

import java.util.Arrays;
import java.util.Random;

/**  
* 类说明   
*  
* @author ****  
* @date 2018年4月1日  新建  
*/
public class RadixSort {
	public static final int SIZE = 10;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}
		
		System.out.println(Arrays.toString(array));
		long time1= System.currentTimeMillis();
		radixSort(array);
		System.out.println(Arrays.toString(array));
		System.out.println(System.currentTimeMillis()-time1);
	}
	
	public static void radixSort(int[] a){
		int num = getMaxLength(a);
		int[][] b = new int[10][a.length+1]; 
		for(int i=1;i<=num;i++){
			for(int j=0;j<a.length;j++){
				int row = getPosNum(a[j], i);
				int col = ++b[row][0];
				b[row][col] = a[j];
			}
			for(int row=0,j=0;row<10;row++){
				for(int col=1;col<=b[row][0];col++){
					a[j++] = b[row][col];
				}
				b[row][0]=0;
			}
		}
	}
	
	public static int getMaxLength(int[] a){
		int max = 0;
		for(int i=0;i<a.length;i++){
			if(a[i]>max){
				max = a[i];
			}
		}
		
		int index = 1;
		while((max/=10)>0){
			index++;
		}
		return index;
	}
	
	public static int getPosNum(int num,int pos){
		int temp= 1;
		for(int i=0;i<pos-1;i++){
			temp *=10;
		}
		return (num/temp)%10;
	}
}
  